package jsc.upComing;

/**
 * This class provides methods to determine the distance beetween two String using the Distance of Levenschtein
 * 
 * @author Maxime Rihouey
 *
 */

public class DistanceDeLevenshtein {

	public static int distanceDeLevenshtein(String a, String b){
		// initialisation
		int lengthA = a.length();
		int lengthB = b.length();
		// matrice M
		int[][] matriceM = new int[lengthB+1][lengthA+1];
		for(int i = 0; i < lengthA+1; i++){
			matriceM[0][i] = i;
		}
		for(int i = 0; i < lengthB+1; i++){
			matriceM[i][0] = i;
		}
		//afficherMatrice(matriceM);

		// matrice Cout
		int[][] matriceCout = new int[lengthB][lengthA];
		for(int i = 0; i < lengthA; i++){
			for(int j = 0; j < lengthB; j++){
				if(a.charAt(i) == b.charAt(j)){
					matriceCout[j][i] = 0;
				}else{
					matriceCout[j][i] = 1;
				}
			}
		}
		//System.out.println("##########################");
		//afficherMatrice(matriceCout);

		// remplissage de matriceM
		for(int i  = 1; i < lengthA+1; i++){
			for(int j = 1; j < lengthB+1; j++){
				matriceM[j][i] = minimum(matriceM[j-1][i]+1, matriceM[j][i-1]+1, matriceM[j-1][i-1]+matriceCout[j-1][i-1]);
			}
		}
		//System.out.println("##########################");
		//afficherMatrice(matriceM);
		return matriceM[lengthB][lengthA];
	}

	public static int minimum(int a, int b, int c){
		if(a < b){
			if(a < c) return a;
			else return c;
		}else if(b < c){
			if(b < a) return b;
			else return a;
		}else if(c < a){
			if(c < b) return c;
			else return b;
		}else return a;
	}

	public static void afficherMatrice(int[][] matrice){
		String affichage = "";
		for(int i = 0; i < matrice.length; i++){
			for(int j = 0; j < matrice[0].length; j++){
				affichage += matrice[i][j]+" ";
			}
			affichage += "\n";
		}
		System.out.println(affichage);
	}
	/**
	 * Main
	 * @param args
	 */
	public static void main(String[] args) {
		String a = "chiens";
		String b = "niche";
		System.out.println(distanceDeLevenshtein(a, b));

		System.out.println("###################");
		System.out.println("abcd".substring(0, 1)+"abcd".substring(2, "abcd".length()));

		System.out.println("###################");
		String word = "salut";
		int i = 0;
		String tronc1 = word.substring(0, i);
		String tronc2 = word.substring(i+1, word.length());

		// 1. suppression d'une lettre
		System.out.println(tronc1+tronc2);

		// 2. ajout d'une lettre
		for(char lettre = 'A'; lettre <= 'Z'; lettre++){
			System.out.println(tronc1+word.charAt(i)+lettre+tronc2);
		}
		for(char lettre = 'a'; lettre <= 'z'; lettre++){
			System.out.println(tronc1+word.charAt(i)+lettre+tronc2);
		}

		// 3. remplacer une lettre
		for(char lettre = 'A'; lettre <= 'Z'; lettre++){
			System.out.println(tronc1+lettre+tronc2);
		}
		for(char lettre = 'a'; lettre <= 'z'; lettre++){
			System.out.println(tronc1+lettre+tronc2);
		}

		// 4. permutation
		if(i+1 < word.length()){
			System.out.println(tronc1+tronc2.substring(0,1)+word.charAt(i)+tronc2.substring(1));
		}
	}
}
